package com.dh.leetcode.five;

import org.junit.Assert;
import org.junit.Test;

import java.util.Arrays;

/**
 * @ClassName: _567_permutation_in_string
 * @Description: 567. 字符串的排列
 * 给定两个字符串 s1 和 s2，写一个函数来判断 s2 是否包含 s1 的排列。
 * <p>
 * 换句话说，第一个字符串的排列之一是第二个字符串的子串。
 * <p>
 * 示例1:
 * <p>
 * 输入: s1 = "ab" s2 = "eidbaooo"
 * 输出: True
 * 解释: s2 包含 s1 的排列之一 ("ba").
 * <p>
 * <p>
 * 示例2:
 * <p>
 * 输入: s1= "ab" s2 = "eidboaoo"
 * 输出: False
 * <p>
 * <p>
 * 注意：
 * <p>
 * 输入的字符串只包含小写字母
 * 两个字符串的长度都在 [1, 10,000] 之间
 * <p>
 * https://leetcode-cn.com/problems/permutation-in-string/
 * @Author: shouzimu
 * @Date: 2021/2/10 14:19
 */
public class _567_permutation_in_string {
    public boolean checkInclusion(String s1, String s2) {
        int s1Length = s1.length();
        int s2Length = s2.length();
        if (s1.length() > s2.length()) {
            return false;
        }
        int[] s1Bucket = new int[26];
        int[] s2Bucket = new int[26];
        for (char c : s1.toCharArray()) {
            s1Bucket[c - 'a']++;
        }

        char[] s2Array = s2.toCharArray();
        for (int i = 0; i < s1.length(); i++) {
            s2Bucket[s2Array[i] - 'a']++;
        }
        if (Arrays.equals(s1Bucket, s2Bucket)) {
            return true;
        }

        for (int i = s1Length; i < s2Length; i++) {
            s2Bucket[s2Array[i - s1Length] - 'a']--;
            s2Bucket[s2Array[i] - 'a']++;
            if (Arrays.equals(s1Bucket, s2Bucket)) {
                return true;
            }
        }
        return false;
    }

    @Test
    public void checkInclusionTest() {
        Assert.assertEquals(true, checkInclusion("ab", "eidbaooo"));
        Assert.assertEquals(true, checkInclusion("abac", "bcaa"));
        Assert.assertEquals(false, checkInclusion("ab", "eidboaoo"));
    }
}
